Excursus: Binomial Coefficients and Pascal's triangle

For $n,i\in \mathbb{N},i\le n$  the binomial coefficient $(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}$ is introduced using the factorial operator ! :

${\displaystyle (\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}≔\frac{n!}{i!(n-i)!}\text{,}}$

[5.0.1]

For $n>0$ we calculate n! by successively multiplying the numbers $\mathrm{1,2,}\dots ,n$. In many cases the partition property $(n+1)!=n!\cdot (n+1)$ is a valuable tool.

We read

• $(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}$ as "n choose i".

• n! as "n-factorial".

  
   

To prove the generalized binomial theorem we need the following properties 1. and 4.

From the condition $i\le n$ we know that there are exactly n + 1 many binomial coefficients for each n. So we have for

$n=0:(\phantom{T}\begin{array}{c}0\\ 0\end{array})\phantom{T}=1$

$n=1:(\phantom{T}\begin{array}{c}1\\ 0\end{array})\phantom{T}=1,(\phantom{T}\begin{array}{c}1\\ 1\end{array})\phantom{T}=1$

$n=2:(\phantom{T}\begin{array}{c}2\\ 0\end{array})\phantom{T}=1,(\phantom{T}\begin{array}{c}2\\ 1\end{array})\phantom{T}=2,(\phantom{T}\begin{array}{c}2\\ 2\end{array})\phantom{T}=1$

If we note down these results centered, row by row we are producing Pascal's triangle, the well known scheme which is expanded up to n = 4 below:

								1
						1				1
				1				2				1
		1				3				3				1
1				4				6				4				1

The above properties 1. to 4. are well reflected in Pascal's triangle:

1. Each row starts with 1 and ends with 1.
    
2. The second number in each row is the line number.
    
3. Every row can be read from left to right and vice versa with no difference.
    
4. Apart from the first and last, every entry in a line is the sum of the two entries above. That means: How far Pascal's triangle might have been constructed, we easily can add a new line without wasting time with the tedious factorials. Let's see how it works in our example:
    

   		1				4				6				4				1
   1				5				10				10				5				1

   
    

Now that the binomial coefficients are at our hand, we easily get concrete binomial formulas from the generalized binomial theorem, take e.g. n = 3 and n = 4:
 

But there are many more properties to be deduced from the generalized binomial theorem.

These results could also be traced in Pascal's triangle:

Every row sum is a power of 2 with the line number for the exponent.   Every alterning row sum equals zero.
The result of each diagonal sum is noted underneath to the right of the last addend.	1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

Another important field for the binomial coefficients is combinatorics. A key sentence here is the following:

Proposition:   Each set M with n elements has exactly $(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}$ many subsets with i elements: $\mid \{N|N\subset M\wedge \mid N\mid =i\}\mid =(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}$ [5.0.9] Proof:  The case i = 0 is nearly done: M has only one subset with 0 elements, namely the empty set, so the assertion follows from [5.0.2]. For $i>0$ we prove by induction: $0\in A:$The precondition $i>0$ leaves nothing to do here, because $i\le n$ is now contradictory. $n\in A\Rightarrow n+1\in A:$Let M be a set with n + 1 elements, say $M=\{a_1,\dots ,a_n,a_{n+1}\}$. We separate the system of all subsets N of M having i elements into two disjoint parts:   Those N, that do not contain $a_{n+1}$. But these are exactly all i-subsets of the n-set $\{a_1,\dots a_n\}$. According to the induction hypothesis there are $(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}$ many of them. Those N, that do contain $a_{n+1}$. Let us assign the set $N\backslash \{a_{n+1}\}$ to each of those. This is obviously a bijective mapping onto the system of all (i − 1)-subsets of $\{a_1,\dots a_n\}$, so we have $(\phantom{T}\begin{array}{c}n\\ i-1\end{array})\phantom{T}$ many sets in this group. All in all (cf. [5.0.5]) M has now $(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}+(\phantom{T}\begin{array}{c}n\\ i-1\end{array})\phantom{T}=(\phantom{T}\begin{array}{c}n+1\\ i\end{array})\phantom{T}$ many subsets with i elements.

From this and [5.0.6] we can deduce a statement on the number of all subsest of M, i.e. the power of the power set of M.

Each n-set M has exactly ${\displaystyle \sum _{i=0}^n(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}=2^n}$ many subsets:

$\mid \mathcal{P}(M)\mid =2^n$

[5.0.10]